package bit_operation;

/**
 * @Description 剑指 Offer 56 - I. 数组中数字出现的次数
 * 位运算、数学（这题第一次写估计没几个人做得出来....理解,背,em...）
 * @Author Firenut
 * @Date 2023-01-25 19:08
 */
public class T56_I_singleNumbers {
    public int[] singleNumbers(int[] nums) {
        int x = 0, y = 1;
        int a = 0, b = 0; // a,b用于保存只出现一次的数字

        // 让所有数字进行异或运算,结果 <==> 只出现一次的那两个数进行异或运算
        // 相同数字异或结果为0,不同数异或结果不为0,即至少有一个二进制位为1
        for (int i = 0; i < nums.length; i++) {
            x ^= nums[i];
        }

        // 让y一直左移,进行与运算,找到x首个值为1的二进制位(从低位往高位的方向)
        while ((y & x) != 0) {
            y <<= 1;
        }

        // 因为要找的那两个a,b 在x首个值为1的二进制位处肯定不相同
        // 而其他数字无所谓,反正它们是成对的,与y进行相与运算肯定结果是相同的，也即分到同一组
        // 而a,b被分到不同组,然后不同组进行 异或运算得到的就是 a,b的最终值
        for (int i = 0; i < nums.length; i++) {
            if ((y & nums[i]) == 0) {
                a ^= nums[i];
            } else {
                b ^= nums[i];
            }
        }
        return new int[]{a,b};
    }
}